package list;

public class MyLinkedList<T> {
    private Node first;
    private Node last;
    private int size = 0;
    private static class Node<T>{
        T item;
        private Node next;
        private Node prev;
        public Node(T e){
            item = e;
        }
    }
    public boolean add(T e){
        //1. 没有元素时候, 增加第一个节点(Node)
        Node<T> node = new Node<>(e);
        if(size==0){
            first = node;
            last = node;
        }else {
            //2. 如果有了 Node 就添加到最后
            last.next = node;
            node.prev = last;
            last = node;
        }
        size++;
        return true;
    }

    public T get(int index){
        if(index<0 || index>=size){
            throw new IndexOutOfBoundsException("index:"+index);
        }
        Node node = findNode(index);
        return (T)node.item;
    }

    private Node findNode(int index){
        Node node;
        if(index<(size>>1)){
            System.out.println("正向查找");
            node = first;
            for(int i = 0; i!=index; i++){
                node = node.next;
            }
        }else{
            System.out.println("反向查找");
            node = last;
            for (int i = size-1; i!=index; i--){
                node = node.prev;
            }
        }
        return node;
    }

    public boolean add(int index, T e){
        if(index == size){ return add(e); }
        if(index<0 || index>size){
            throw new IndexOutOfBoundsException("index:"+index);
        }
        Node newNode = new Node(e);
        if (index==0){
            newNode.next = first;
            first.prev = newNode;
            first = newNode;
        }else {
            Node node = findNode(index);
            Node prev = node.prev;
            prev.next = newNode;
            newNode.next = node;
            node.prev = newNode;
            newNode.prev = prev;
        }
        size++;
        return true;
    }

    @Override
    public String toString() {
        if(size == 0) {
            return "[]";
        }
        // buffer 缓存
        StringBuilder buf = new StringBuilder("[");
        buf.append(first.item);
        Node node = first.next;
        while(node != null){
            buf.append(", ").append(node.item);
            node = node.next;
        }
        return buf.append("]").toString();
    }
}
